package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * @author haomin
 * @date 2022/07/17 07:51
 **/
public class Day3_1_Num22_GenerateParenthesis {
    public List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, n, "");
        return result;
    }

    // 回溯
    public void dfs(int left, int right, String target){
        // 当左右括号匹配完时，添加到result中
        if(left == 0 && right == 0){
            result.add(target);
            return;
        }
        // 左括号有剩余，先拼接左括号
        if(left > 0){
            dfs(left-1, right, target+"(");
        }
        // 当右括号剩余数大于左括号剩余数，拼接右括号
        if(right > left){
            dfs(left, right-1, target+")");
        }
    }
}